{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Swap For Longest Repeated Character Substring"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #hash-table #string #sliding-window"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #哈希表 #字符串 #滑动窗口"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: maxRepOpt1"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #单字符重复子串的最大长度"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>如果字符串中的所有字符都相同，那么这个字符串是单字符重复的字符串。</p>\n",
    "\n",
    "<p>给你一个字符串&nbsp;<code>text</code>，你只能交换其中两个字符一次或者什么都不做，然后得到一些单字符重复的子串。返回其中最长的子串的长度。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>text = &quot;ababa&quot;\n",
    "<strong>输出：</strong>3\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>text = &quot;aaabaaa&quot;\n",
    "<strong>输出：</strong>6\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>text = &quot;aaabbaaa&quot;\n",
    "<strong>输出：</strong>4\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 4：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>text = &quot;aaaaa&quot;\n",
    "<strong>输出：</strong>5\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 5：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>text = &quot;abcdef&quot;\n",
    "<strong>输出：</strong>1\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= text.length &lt;= 20000</code></li>\n",
    "\t<li><code>text</code> 仅由小写英文字母组成。</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [swap-for-longest-repeated-character-substring](https://leetcode.cn/problems/swap-for-longest-repeated-character-substring/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [swap-for-longest-repeated-character-substring](https://leetcode.cn/problems/swap-for-longest-repeated-character-substring/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['\"ababa\"', '\"aaabaaa\"', '\"aaaaa\"']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxRepOpt1(self, text: str) -> int:\n",
    "     res = i = 0\n",
    "     cnt = Counter(text)\n",
    "     while i < len(text):\n",
    "        j = i\n",
    "        while j < len(text) and text[j] == text[i]:\n",
    "            j += 1\n",
    "        cur_cnt = j - i\n",
    "        k = j + 1\n",
    "        while k < len(text) and text[k] == text[i]:\n",
    "            k += 1\n",
    "        res = max(res, min(cur_cnt + k - j , cnt[text[i]]))\n",
    "        i = j\n",
    "     return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxRepOpt1(self, text: str) -> int:\n",
    "        num=Counter(text) #代码作用是计算出字符串中不同元素出现的个数的数量\n",
    "        changdu=len(text)  #返回对象中元素的长度\n",
    "        sum=0\n",
    "        i=0\n",
    "\n",
    "        while i<changdu:\n",
    "            b=i\n",
    "            while b<changdu and text[b]==text[i]:\n",
    "                b+=1\n",
    "            l=b-i\n",
    "            k=b+1\n",
    "\n",
    "\n",
    "\n",
    "            while k<changdu and text[k]==text[i]:\n",
    "                k+=1\n",
    "            r=k-b-1\n",
    "            sum=max(sum,min(l+r+1,num[text[i]]))\n",
    "            i=b\n",
    "        return sum"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxRepOpt1(self, text: str) -> int:\n",
    "      count=Counter(text)\n",
    "      res=0\n",
    "      i=0\n",
    "      while i<len(text):\n",
    "        j=i\n",
    "        while j<len(text) and text[j]==text[i]:\n",
    "          j+=1\n",
    "        cnt=j-i\n",
    "        if cnt<count[text[i]] and (j<len(text) or i>0):\n",
    "          res=max(res,cnt+1)\n",
    "        k=j+1\n",
    "        while k<len(text) and text[k]==text[i]:\n",
    "          k+=1\n",
    "        res=max(res,min(k-i,count[text[i]]))\n",
    "        i=j\n",
    "      return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxRepOpt1(self, text: str) -> int:\n",
    "        cnt = Counter(text)\n",
    "        n = len(text)\n",
    "        ans = i = 0\n",
    "        while i < n:\n",
    "            j = i\n",
    "            while j < n and text[j] == text[i]:\n",
    "                j += 1\n",
    "            l = j - i\n",
    "            k = j + 1\n",
    "            while k < n and text[k] == text[i]:\n",
    "                k += 1\n",
    "            r = k - j - 1\n",
    "            ans = max(ans, min(l + r + 1, cnt[text[i]]))\n",
    "            i = j\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxRepOpt1(self, text: str) -> int:\n",
    "        char_count = {}\n",
    "        for char in text:\n",
    "            if char in char_count:\n",
    "                char_count[char] += 1\n",
    "            else:\n",
    "                char_count[char] = 1\n",
    "        \n",
    "        text_length = len(text)\n",
    "        max_repeated = 0\n",
    "        i = 0\n",
    "        while i < text_length:\n",
    "            j = i\n",
    "            while j < text_length and text[j] == text[i]:\n",
    "                j += 1\n",
    "            left_length = j - i\n",
    "            k = j + 1\n",
    "            while k < text_length and text[k] == text[i]:\n",
    "                k += 1\n",
    "            right_length = k - j - 1\n",
    "            max_repeated = max(max_repeated, min(left_length + right_length + 1, char_count[text[i]]))\n",
    "            i = j\n",
    "        return max_repeated"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxRepOpt1(self, text: str) -> int:\n",
    "        n = len(text)\n",
    "        counter = Counter(text) # 统计每个字符的个数，用于决定最大长度是否能+1\n",
    "        res = i = 0\n",
    "        while i < n:\n",
    "            c = text[i]  # 当前字符\n",
    "\n",
    "            # 找出第一段连续字符串\n",
    "            r1 = i\n",
    "            while r1 < n and text[r1] == c: r1 += 1\n",
    "            len1 = r1 - i   # 第一段连续字符串的长度\n",
    "\n",
    "            # 各种分类讨论。主要是len1 + len2 < counter[c]的话最长度可以+1。\n",
    "            if r1 == n: # 到text最后一个位置，不需要找第二段连续字符串了\n",
    "                if len1 < counter[c]:\n",
    "                    res = max(res, len1 + 1)\n",
    "                else:\n",
    "                    res = max(res, len1)\n",
    "                break # 可以不加这行，加上去好理解一点。到text最后一个位置处理完可以直接return了\n",
    "\n",
    "            # 跳个字符，继续找出第二段连续字符串\n",
    "            r2 = r1 + 1\n",
    "            while r2 < n and text[r2] == c: r2 += 1\n",
    "            len2 = r2 - (r1 + 1)  # 第二段连续字符串的长度\n",
    "\n",
    "            # 各种分类讨论。主要是len1 + len2 < counter[c]的话最长度可以+1\n",
    "            if len1 + len2 < counter[c]:\n",
    "                res = max(res, len1 + len2 + 1)\n",
    "            else:\n",
    "                res = max(res, len1 + len2)\n",
    "            i = r1  # 直接从第一段连续字符串后开始找，因为[r1-i, r1)这个区间的res都不会比i位置的再长了。\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxRepOpt1(self, text: str) -> int:\n",
    "        cnt = Counter(text)\n",
    "        ans = 0\n",
    "        k1, k2, c1, c2 = \"\", \"\", 0, 0\n",
    "        for k, li in groupby(text):\n",
    "            length = len(list(li))\n",
    "            if k == k1 and c2 == 1:\n",
    "                ans = max(ans, c1+length+(cnt[k]>(c1+length)))\n",
    "            else:\n",
    "                ans = max(ans, length+(cnt[k]>length))\n",
    "            k1, k2, c1, c2 = k2, k, c2, length\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxRepOpt1(self, text: str) -> int:\n",
    "        cnt = Counter(text)\n",
    "        n = len(text)\n",
    "        ans = i = 0\n",
    "        while i < n:\n",
    "            j = i\n",
    "            while j < n and text[j] == text[i]:\n",
    "                j += 1\n",
    "            l = j - i\n",
    "            k = j + 1\n",
    "            while k < n and text[k] == text[i]:\n",
    "                k += 1\n",
    "            r = k - j - 1\n",
    "            ans = max(ans, min(l + r + 1, cnt[text[i]]))\n",
    "            i = j\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxRepOpt1(self, text: str) -> int:\n",
    "        # 感觉是滑动窗口，这个窗口里面只能有两个字母，并且\n",
    "        # 窗口当中的内容 \n",
    "        hashmap = {}\n",
    "        count = Counter(text)\n",
    "        def check(hashmap):\n",
    "            if len(hashmap) > 2:\n",
    "                return True \n",
    "            if len(hashmap) == 1:\n",
    "                return False\n",
    "            if len(hashmap) == 2:\n",
    "                k1,k2 = hashmap.keys()\n",
    "                if hashmap[k1] == 1 or hashmap[k2] == 1:\n",
    "                    if hashmap[k1] == 1:\n",
    "                        if hashmap[k2] < count[k2]:\n",
    "                            return False\n",
    "                        else:\n",
    "                            return True\n",
    "                    if hashmap[k2] == 1:\n",
    "                        if hashmap[k1] < count[k1]:\n",
    "                            return False\n",
    "                        else:\n",
    "                            return True\n",
    "                if hashmap[k1] > 1 and hashmap[k2] > 1:\n",
    "                    return True \n",
    "        \n",
    "        # 收集答案\n",
    "        res = 0\n",
    "        left = 0\n",
    "        for right in range(len(text)):\n",
    "            if text[right] in hashmap:\n",
    "                hashmap[text[right]] += 1\n",
    "            else:\n",
    "                hashmap[text[right]] = 1\n",
    "            # 当不满足条件的时候\n",
    "            while check(hashmap):\n",
    "                if hashmap[text[left]] == 1:\n",
    "                    del hashmap[text[left]]\n",
    "                else:\n",
    "                    hashmap[text[left]] -= 1\n",
    "                left += 1\n",
    "            res = max(res,right-left+1)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxRepOpt1(self, text: str) -> int:\n",
    "        cnt = collections.Counter(text)\n",
    "        ans = i = 0\n",
    "        n = len(text)\n",
    "        while i < n:\n",
    "            j = i\n",
    "            while j < n and text[j] == text[i]:\n",
    "                j += 1\n",
    "            l = j - i \n",
    "            k = j + 1\n",
    "            while k < n and text[k] == text[i]:\n",
    "                k += 1\n",
    "            r = k - j - 1\n",
    "            ans = max(ans, min(l + r + 1, cnt[text[i]]))\n",
    "            i = j\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxRepOpt1(self, text: str) -> int:\n",
    "        i = 0\n",
    "        max_len = 0\n",
    "        cnt = Counter(text)\n",
    "        while i < len(text):\n",
    "            j = i\n",
    "            while j < len(text) and text[j] == text[i]:\n",
    "                j += 1\n",
    "            k = j+1\n",
    "            while k < len(text) and text[k] == text[i]:\n",
    "                k += 1\n",
    "            max_len=max(max_len, min(k-i, cnt[text[i]]))\n",
    "            i = j\n",
    "        return max_len\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxRepOpt1(self, text: str) -> int:\n",
    "        cnt = Counter(text)\n",
    "        def check():\n",
    "            k1, k2 = list(d.keys())\n",
    "            val1, val2 = d[k1], d[k2]\n",
    "            if val1 == val2:\n",
    "                if d[k1] < cnt[k1] or d[k2] < cnt[k2]:\n",
    "                    return True\n",
    "            elif val1 < val2:\n",
    "                if d[k2] < cnt[k2]:\n",
    "                    return True\n",
    "            else:\n",
    "                if d[k1] < cnt[k1]:\n",
    "                    return True\n",
    "            return False\n",
    "\n",
    "        d, l, res = Counter(), 0, 0\n",
    "        for r, c in enumerate(text):\n",
    "            d[c] += 1\n",
    "            while len(d) > 2 or (len(d) == 2 and min(d.values()) > 1):\n",
    "                d[text[l]] -= 1\n",
    "                if d[text[l]] == 0:\n",
    "                    d.pop(text[l])\n",
    "                l += 1\n",
    "            if len(d) == 2:\n",
    "                if check():\n",
    "                    res = max(res, r - l + 1)\n",
    "                else:\n",
    "                    res = max(res, r - l)\n",
    "            else:\n",
    "                res = max(res, r - l + 1)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxRepOpt1(self, text: str) -> int:\n",
    "        word_list = [0 for i in range(26)]\n",
    "        for n in text:\n",
    "            word_list[ord(n)-97] += 1\n",
    "        max_length = 1\n",
    "        for i in range(26):\n",
    "            if word_list[i] <= max_length:\n",
    "                continue\n",
    "            chr_i = chr(i + 97)\n",
    "            index1 = -1\n",
    "            index2 = -1\n",
    "            index3 = -1\n",
    "            for index, n in enumerate(text):\n",
    "                if n == chr_i:\n",
    "                    if index1 == -1:\n",
    "                        index1 = index\n",
    "                    elif index2 != -1 and index3 == -1:\n",
    "                        if index - index2 == 2:\n",
    "                            index3 = index\n",
    "                        else:\n",
    "                            if index2 - index1 + 1 == word_list[i]:\n",
    "                                max_length = max(index2 - index1 + 1, max_length)\n",
    "                            else:\n",
    "                                max_length = max(index2 - index1 + 2, max_length)\n",
    "                            index1 = index\n",
    "                            index2 = -1\n",
    "                else:\n",
    "                    if index3 != -1:\n",
    "                        if index - index3 + index2 - index1 + 1 == word_list[i]:\n",
    "                            max_length = max(index - index3 + index2 - index1 + 1,max_length)\n",
    "                        else:\n",
    "                            max_length = max(index - index3 + index2 - index1 + 2,max_length)\n",
    "                        index1 = index3\n",
    "                        index2 = index - 1\n",
    "                        index3 = -1\n",
    "                    elif index1 != -1 and index2 == -1:\n",
    "                        index2 = index - 1\n",
    "            if index3 != -1:\n",
    "                if index - index3 + index2 - index1 + 2 == word_list[i]:\n",
    "                    max_length = max(index - index3 + index2 - index1 + 2,max_length)\n",
    "                else:\n",
    "                    max_length = max(index - index3 + index2 - index1 + 3,max_length)\n",
    "            elif index2 != -1:\n",
    "                if index2 - index1 + 1 == word_list[i]:\n",
    "                    max_length = max(index2 - index1 + 1, max_length)\n",
    "                else:\n",
    "                    max_length = max(index2 - index1 + 2, max_length)\n",
    "            elif index1 != -1:\n",
    "                if len(text) - index1 == word_list[i]:\n",
    "                    max_length = max(len(text) - index1, max_length)\n",
    "                else:\n",
    "                    max_length = max(len(text) - index1 + 1, max_length)\n",
    "        return max_length\n",
    "                    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxRepOpt1(self, text: str) -> int:\n",
    "        if len(text) == 1:\n",
    "            return 1\n",
    "        count = Counter(text)\n",
    "        currchar = text[0]\n",
    "        currcharcount = 1\n",
    "        res = 0\n",
    "        for i in range(1, len(text)):\n",
    "            if text[i]!=currchar: #检查到不相等的字符\n",
    "                searchidx = i+1 #向后统计currchar\n",
    "                while searchidx < len(text) and text[searchidx] == currchar:\n",
    "                    currcharcount += 1\n",
    "                    searchidx += 1\n",
    "                if currcharcount < count[currchar]: #和总数比较，小于总数还可以 + 1\n",
    "                    currcharcount += 1\n",
    "                res = max(res, currcharcount) #更新答案\n",
    "                currcharcount = 1\n",
    "                currchar = text[i]\n",
    "            else: #查到相同的字符就增加个数\n",
    "                currcharcount += 1\n",
    "        #最后在检查，更新答案一次\n",
    "        if currcharcount > 1:\n",
    "            if currcharcount < count[currchar]:\n",
    "                currcharcount += 1\n",
    "            res = max(res, currcharcount)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxRepOpt1(self, text: str) -> int:\n",
    "        dt = [0] *26\n",
    "        cnt = [0] * 26\n",
    "\n",
    "        count = Counter(text)\n",
    "\n",
    "        res = 0\n",
    "        n = len(text)\n",
    "        i = 0\n",
    "\n",
    "        while i < n:\n",
    "            j = i\n",
    "            while j < n and text[j] == text[i]:\n",
    "                j+=1\n",
    "            res = max(res, j-i)\n",
    "\n",
    "            curcnt = j - i\n",
    "            if curcnt < count[text[i]]:\n",
    "                res = max(res, curcnt + 1)\n",
    "            k = j+1\n",
    "            while k < n and text[k] == text[i]:\n",
    "                k += 1\n",
    "            res = max(res, min(k-i, count[text[i]]))\n",
    "            i = j\n",
    "        return res\n",
    "\n",
    "\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxRepOpt1(self, text: str) -> int:\n",
    "        n = len(text)\n",
    "        text = list(text)\n",
    "        start,end = 0,1\n",
    "        ans = 1\n",
    "        while start < n:\n",
    "            end = start+1\n",
    "            if ans >= n-start:\n",
    "                break\n",
    "            while end < n:\n",
    "                chSet = Counter(text[start:end+1])\n",
    "                if len(chSet) == 1:\n",
    "                    ans = max(ans, end-start+1)\n",
    "                elif len(chSet) == 2:\n",
    "                    v1,k2 = 0,''\n",
    "                    for k,v in chSet.items():\n",
    "                        if v == 1 and v1 == 0:\n",
    "                            v1 = v\n",
    "                        else:\n",
    "                            k2 = k\n",
    "                    if v1 == 1 and (k2 in text[:start] or k2 in text[end+1:]):\n",
    "                        ans = max(ans,end-start+1)\n",
    "                    else:\n",
    "                        break\n",
    "                else:\n",
    "                    break\n",
    "                end += 1\n",
    "            start += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxRepOpt1(self, text: str) -> int:\n",
    "        if len(text) < 2:\n",
    "            return len(text)\n",
    "        maxl = len(text)\n",
    "        toRight, toLeft = [1] * maxl, [1] * maxl\n",
    "        cnt = [0] * 26\n",
    "        maxSub = 0\n",
    "        for c in text:\n",
    "            cnt[ord(c) - ord('a')] += 1\n",
    "        for i in range(1, maxl):\n",
    "            toLeft[i] = (toLeft[i - 1] if text[i] == text[i - 1] else 0) + 1\n",
    "        for i in range(maxl - 2, -1, -1):\n",
    "            toRight[i] = (toRight[i + 1] if text[i] == text[i + 1] else 0) + 1\n",
    "        # print(toLeft)\n",
    "        # print(toRight)\n",
    "        # print(cnt)\n",
    "        for i in range(1, maxl):\n",
    "            t = (0 if toLeft[i - 1] == cnt[ord(text[i - 1]) - ord('a')] else 1) + toLeft[i - 1]\n",
    "            if t > maxSub:\n",
    "                    maxSub = t\n",
    "        for i in range(maxl - 1):\n",
    "            t = (0 if toRight[i + 1] == cnt[ord(text[i + 1]) - ord('a')] else 1) + toRight[i + 1]\n",
    "            if t > maxSub:\n",
    "                    maxSub = t\n",
    "        for i in range(1, maxl - 1):\n",
    "            if text[i - 1] == text[i + 1]:\n",
    "                if toLeft[i - 1] + toRight[i + 1] == cnt[ord(text[i - 1]) - ord('a')]:\n",
    "                    t = toLeft[i - 1] + toRight[i + 1]\n",
    "                else:\n",
    "                    t = toLeft[i - 1] + toRight[i + 1] + 1\n",
    "                if t > maxSub:\n",
    "                    maxSub = t\n",
    "        return maxSub\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxRepOpt1(self, text: str) -> int:\n",
    "      countMap = collections.defaultdict(int)\n",
    "      for c in list(text):\n",
    "        countMap[c] += 1\n",
    "      n = len(text)\n",
    "      def solution(text):\n",
    "        ret = 0\n",
    "        leftPtr=0\n",
    "        while leftPtr < n:\n",
    "          rightPtr = leftPtr\n",
    "          while rightPtr < n and text[leftPtr] == text[rightPtr]:\n",
    "            rightPtr+=1\n",
    "          repLen = rightPtr-leftPtr\n",
    "          repChar = text[leftPtr]\n",
    "          tempPtr = rightPtr\n",
    "          diffCount = 0\n",
    "          while repLen < countMap[repChar] and tempPtr < n and diffCount < 1:\n",
    "            if text[tempPtr] != repChar:\n",
    "              diffCount+=1\n",
    "              tempPtr+=1\n",
    "              repLen+=1\n",
    "            else:\n",
    "              tempPtr+=1\n",
    "              repLen+=1\n",
    "          while tempPtr < n and repLen < countMap[repChar] and text[tempPtr] == repChar:\n",
    "            tempPtr+=1\n",
    "            repLen+=1\n",
    "          print(leftPtr, repLen)\n",
    "          ret = max(ret, repLen)\n",
    "          leftPtr = rightPtr\n",
    "        return ret\n",
    "      return max(solution(text), solution(text[::-1]))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxRepOpt1(self, text: str) -> int:\n",
    "        length = len(text)\n",
    "        counter = collections.Counter(text)\n",
    "        if len(counter) == 1:\n",
    "            pass#return length\n",
    "        lc, rc = [0]*length, [0]*length\n",
    "        le = 0\n",
    "        for ri in range(length-1):\n",
    "            if text[ri] != text[le]:\n",
    "                le = ri\n",
    "            lc[ri+1] = ri - le + 1\n",
    "        ri = length-1\n",
    "        for le in range(length-1, 0, -1):\n",
    "            if text[le] != text[ri]:\n",
    "                ri = le\n",
    "            rc[le-1] = ri - le + 1\n",
    "        res = max(min(rc[0]+1, counter[text[0]]), min(lc[-1]+1, counter[text[-1]]))\n",
    "        for i in range(1, length-1):\n",
    "            if text[i-1] == text[i+1]:\n",
    "                res = max(res, min(lc[i]+rc[i]+1, counter[text[i-1]]))\n",
    "            else:\n",
    "                res = max(res, min(lc[i]+1, counter[text[i-1]]), min(rc[i]+1, counter[text[i+1]]))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxRepOpt1(self, text: str) -> int:\n",
    "        str_list = list(text)\n",
    "        str_set = set(text)\n",
    "        length_str = len(str_list)\n",
    "        if length_str == len(str_set):\n",
    "            return 1\n",
    "        else:\n",
    "            i = 0\n",
    "            j = 1\n",
    "            result = 0\n",
    "            while i < length_str - 1:\n",
    "                tmp_str = str_list[i]\n",
    "                sub_str_num = str_list.count(tmp_str)\n",
    "                str_list_copy = str_list.copy()\n",
    "                while j < length_str and tmp_str == str_list[j]:\n",
    "                    j += 1\n",
    "                k = j\n",
    "                j += 1\n",
    "                while j < length_str and tmp_str == str_list_copy[j]:\n",
    "                    j += 1\n",
    "                result = max(result, min(j - i, sub_str_num))\n",
    "                i = k\n",
    "                j = i + 1\n",
    "            return result\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxRepOpt1(self, text: str) -> int:\n",
    "        # 双指针, O(n)\n",
    "        # cnt = Counter(text)\n",
    "        # i, n = 0, len(text)\n",
    "        # ans = 0\n",
    "\n",
    "        # while i < n:\n",
    "        #     j = i\n",
    "        #     while j < n and text[j] == text[i]:\n",
    "        #         j += 1\n",
    "        #     l = j - 1\n",
    "        #     k = j + 1\n",
    "        #     while k < n and text[k] == text[i]:\n",
    "        #         k += 1\n",
    "        #     r = k - j - 1\n",
    "        #     ans = max(ans, min(l + r + 1, cnt[text[i]]))\n",
    "        #     i = j\n",
    "        # return ans\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        cnt = Counter(text)\n",
    "        print(cnt)\n",
    "        n = len(text)\n",
    "        ans = i = 0\n",
    "        while i < n:\n",
    "            j = i + 1\n",
    "            while j < n and text[j] == text[i]:\n",
    "                j += 1\n",
    "            l = j - i\n",
    "            k = j + 1\n",
    "            while k < n and text[k] == text[i]:\n",
    "                k += 1\n",
    "            r = k - j - 1\n",
    "            ans = max(ans, min(l + r + 1, cnt[text[i]]))\n",
    "            print('cnt: ', l + r + 1, cnt[text[i]])\n",
    "            i = j\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxRepOpt1(self, text: str) -> int:\n",
    "        cnt = Counter(text)\n",
    "        count = Counter()\n",
    "        def check():\n",
    "            k1, k2 = list(d.keys())\n",
    "            val1, val2 = d[k1], d[k2]\n",
    "            print((k1, val1), (k2, val2))\n",
    "            if val1 == val2:\n",
    "                print(count, cnt)\n",
    "                if d[k1] < cnt[k1] or d[k2] < cnt[k2]:\n",
    "                    return True\n",
    "            elif val1 < val2:\n",
    "                if d[k2] < cnt[k2]:\n",
    "                    return True\n",
    "            else:\n",
    "                if d[k1] < cnt[k1]:\n",
    "                    return True\n",
    "            return False\n",
    "\n",
    "        d, l, res = Counter(), 0, 0\n",
    "        for r, c in enumerate(text):\n",
    "            d[c] += 1\n",
    "            count[c] += 1\n",
    "            while len(d) > 2 or (len(d) == 2 and min(d.values()) > 1):\n",
    "                d[text[l]] -= 1\n",
    "                if d[text[l]] == 0:\n",
    "                    d.pop(text[l])\n",
    "                l += 1\n",
    "            if len(d) == 2:\n",
    "                if check():\n",
    "                    res = max(res, r - l + 1)\n",
    "                else:\n",
    "                    res = max(res, r - l)\n",
    "            else:\n",
    "                res = max(res, r - l + 1)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    \n",
    "    def maxRepOpt1(self, text: str) -> int:\n",
    "        newt = [c for c in text]\n",
    "        newt.reverse()\n",
    "        reverseText = ''.join(newt)\n",
    "        return max(self.maxRepOpt(text), self.maxRepOpt(reverseText))\n",
    "\n",
    "    def maxRepOpt(self, text: str) -> int:\n",
    "        N = len(text)\n",
    "        lenOfRepeateStartAt = [1]*N\n",
    "        mdict = defaultdict(int)\n",
    "\n",
    "        rst = 1\n",
    "        i = j = 0\n",
    "        while j < N:\n",
    "            while j < N and text[j] == text[i]:\n",
    "                j += 1\n",
    "            if j <= N:\n",
    "                lenOfRepeateStartAt[i] = j-i\n",
    "                mdict[text[i]] += j-i\n",
    "                rst = max(rst, j-i)\n",
    "                i = j\n",
    "\n",
    "        i = 0\n",
    "        while i < N:\n",
    "            j = lenOfRepeateStartAt[i] + i\n",
    "            mlen = j-i\n",
    "            if j < N:\n",
    "                if mdict[text[i]] > mlen:\n",
    "                    mlen += 1\n",
    "                if j+1 < N and text[j+1] == text[i]:\n",
    "                    newj = lenOfRepeateStartAt[j+1] + j+1\n",
    "                    mlen = lenOfRepeateStartAt[j+1] + lenOfRepeateStartAt[i]\n",
    "                    if mlen < mdict[text[i]]:\n",
    "                        mlen += 1\n",
    "            rst = max(rst, mlen)\n",
    "            i = j\n",
    "        return rst\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxRepOpt1(self, text: str) -> int:\n",
    "        \n",
    "        from collections import defaultdict\n",
    "        dic=defaultdict(int)\n",
    "        for i in text: dic[i]+=1\n",
    "\n",
    "        dic2=copy.copy(dic)\n",
    "\n",
    "        res=0\n",
    "        lastvalue=text[0]\n",
    "        lastcount=1\n",
    "        dic[text[0]] -= 1\n",
    "        if not dic[text[0]]: del dic[text[0]]\n",
    "        currentvalue=\"\"\n",
    "        currentcount=0\n",
    "        i=1\n",
    "\n",
    "        while i<len(text) and text[i]==lastvalue:\n",
    "            dic[text[i]] -= 1\n",
    "            if not dic[text[i]]: del dic[text[i]]\n",
    "            lastcount+=1\n",
    "            i+=1\n",
    "        if lastvalue in dic:\n",
    "            res = max(res, lastcount + 1)\n",
    "        else:\n",
    "            res = max(res, lastcount)\n",
    "\n",
    "        if i<len(text):\n",
    "            dic[text[i]] -= 1\n",
    "            if not dic[text[i]]: del dic[text[i]]\n",
    "            currentvalue=text[i]\n",
    "            currentcount=1\n",
    "            i+=1\n",
    "\n",
    "        while i<len(text):\n",
    "            dic[text[i]]-=1\n",
    "            if not dic[text[i]]: del dic[text[i]]\n",
    "            if text[i]!=currentvalue:\n",
    "                if currentcount!=1:\n",
    "                    lastvalue=currentvalue\n",
    "                    lastcount=currentcount\n",
    "                    if currentvalue in dic: res=max(res,currentcount+1)\n",
    "                    else: res=max(res,currentcount)\n",
    "                    currentvalue=text[i]\n",
    "                    currentcount=1\n",
    "                else:\n",
    "                    j=i+1\n",
    "                    count=1\n",
    "                    while j<len(text) and text[j]==text[i]:\n",
    "                        if text[j] in dic:\n",
    "                            dic[text[j]]-=1\n",
    "                            if not dic[text[j]]: del dic[text[j]]\n",
    "                        j+=1\n",
    "                        count+=1\n",
    "                    if text[i]==lastvalue:  #如果上面j==len(text)，则此时dic为空\n",
    "                        if text[i] in dic: res=max(res,lastcount+count+1)\n",
    "                        else: res=max(res,lastcount+count)\n",
    "                    res=max(res,count)\n",
    "                    lastvalue=currentvalue\n",
    "                    lastcount=currentcount\n",
    "                    currentvalue=text[i]\n",
    "                    currentcount=count\n",
    "                    i=j\n",
    "                    continue\n",
    "            else: currentcount+=1\n",
    "            i+=1\n",
    "\n",
    "        res=max(res,currentcount)\n",
    "\n",
    "        dic=dic2\n",
    "        text=\"\".join(reversed(text))\n",
    "        lastvalue=text[0]\n",
    "        lastcount=1\n",
    "        dic[text[0]] -= 1\n",
    "        if not dic[text[0]]: del dic[text[0]]\n",
    "        currentvalue=\"\"\n",
    "        currentcount=0\n",
    "        i=1\n",
    "\n",
    "        while i<len(text) and text[i]==lastvalue:\n",
    "            dic[text[i]] -= 1\n",
    "            if not dic[text[i]]: del dic[text[i]]\n",
    "            lastcount+=1\n",
    "            i+=1\n",
    "        if lastvalue in dic:\n",
    "            res = max(res, lastcount + 1)\n",
    "        else:\n",
    "            res = max(res, lastcount)\n",
    "\n",
    "        if i<len(text):\n",
    "            dic[text[i]] -= 1\n",
    "            if not dic[text[i]]: del dic[text[i]]\n",
    "            currentvalue=text[i]\n",
    "            currentcount=1\n",
    "            i+=1\n",
    "\n",
    "        while i<len(text):\n",
    "            dic[text[i]]-=1\n",
    "            if not dic[text[i]]: del dic[text[i]]\n",
    "            if text[i]!=currentvalue:\n",
    "                if currentcount!=1:\n",
    "                    lastvalue=currentvalue\n",
    "                    lastcount=currentcount\n",
    "                    if currentvalue in dic: res=max(res,currentcount+1)\n",
    "                    else: res=max(res,currentcount)\n",
    "                    currentvalue=text[i]\n",
    "                    currentcount=1\n",
    "                else:\n",
    "                    j=i+1\n",
    "                    count=1\n",
    "                    while j<len(text) and text[j]==text[i]:\n",
    "                        if text[j] in dic:\n",
    "                            dic[text[j]]-=1\n",
    "                            if not dic[text[j]]: del dic[text[j]]\n",
    "                        j+=1\n",
    "                        count+=1\n",
    "                    if text[i]==lastvalue:  #如果上面j==len(text)，则此时dic为空\n",
    "                        if text[i] in dic: res=max(res,lastcount+count+1)\n",
    "                        else: res=max(res,lastcount+count)\n",
    "                    res=max(res,count)\n",
    "                    lastvalue=currentvalue\n",
    "                    lastcount=currentcount\n",
    "                    currentvalue=text[i]\n",
    "                    currentcount=count\n",
    "                    i=j\n",
    "                    continue\n",
    "            else: currentcount+=1\n",
    "            i+=1\n",
    "\n",
    "        res=max(res,currentcount)\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxRepOpt1(self, text: str) -> int:\n",
    "        l,r = 0,0\n",
    "        n = len(text)\n",
    "        text = list(text)\n",
    "        def get_farest_val(val):\n",
    "            for i in range(n):\n",
    "                if text[n-1-i] == val:\n",
    "                    return n-1-i\n",
    "            return -1\n",
    "        ans = 1\n",
    "        while r < n:\n",
    "            if text[l] == text[r]:\n",
    "                r+=1\n",
    "                if r == n:\n",
    "                    ans = max(ans,r-l)\n",
    "            else:\n",
    "                idx = get_farest_val(text[l])\n",
    "                if idx < r:\n",
    "                    ans = max(ans,r-l)\n",
    "                    l=r\n",
    "                else:\n",
    "                    text[idx] = text[r]\n",
    "                    text[r] = text[l]\n",
    "                    prev = r\n",
    "                    while r < n and text[l] == text[r]:\n",
    "                        r+=1\n",
    "                    # print(r,l,text)\n",
    "                    ans = max(ans,r-l)\n",
    "                    text[prev] = text[idx]\n",
    "                    text[idx] = text[l]\n",
    "                    # print(text)\n",
    "                    l = prev\n",
    "                    r = prev\n",
    "        text = text[::-1]\n",
    "        print(text)\n",
    "        l,r=0,0\n",
    "        while r < n:\n",
    "            if text[l] == text[r]:\n",
    "                r+=1\n",
    "                if r == n:\n",
    "                    ans = max(ans,r-l)\n",
    "            else:\n",
    "                idx = get_farest_val(text[l])\n",
    "                # print(idx)\n",
    "                if idx < r:\n",
    "                    ans = max(ans,r-l)\n",
    "                    l=r\n",
    "                else:\n",
    "                    text[idx] = text[r]\n",
    "                    text[r] = text[l]\n",
    "                    prev = r\n",
    "                    while r < n and text[l] == text[r]:\n",
    "                        r+=1\n",
    "                    # print(r,l,idx,text)\n",
    "                    ans = max(ans,r-l)\n",
    "                    text[prev] = text[idx]\n",
    "                    text[idx] = text[l]\n",
    "                    # print(text)\n",
    "                    l = prev\n",
    "                    r = prev\n",
    "        return ans\n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxRepOpt1(self, text: str) -> int:\n",
    "        counter = Counter(text)\n",
    "        \n",
    "        matches = re.finditer(r\"(.)\\1*\", text)\n",
    "        matches_lst = list(map(lambda x: x.group(), matches))\n",
    "        n = len(matches_lst)\n",
    "        max_len = 0\n",
    "        for i in range(n):\n",
    "            cur_char = matches_lst[i][0]\n",
    "            cur_len = len(matches_lst[i])\n",
    "            if i<n-2:\n",
    "                if (len(matches_lst[i+1])==1) and (matches_lst[i+2][0]==cur_char):\n",
    "                    cur_len += len(matches_lst[i+2])\n",
    "            if counter[cur_char] > cur_len:\n",
    "                cur_len += 1\n",
    "            max_len = max(cur_len, max_len)\n",
    "\n",
    "        return max_len"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    \n",
    "\n",
    "    def maxRepOpt1(self, text: str) -> int:\n",
    "        N = len(text)\n",
    "        count = Counter(text)\n",
    "        i = j = k = 0\n",
    "        rst = 1\n",
    "        while i < N:\n",
    "            j = i+1\n",
    "            while j < N and text[j] == text[i]:\n",
    "                j += 1\n",
    "            k = j+1\n",
    "            while k < N and text[k] == text[i]:\n",
    "                k += 1\n",
    "            rst = min(k-i-1, count[text[i]])\n",
    "            i = j\n",
    "        return rst\n",
    "\n",
    "    def maxRepOpt1(self, text: str) -> int:\n",
    "        newt = [c for c in text]\n",
    "        newt.reverse()\n",
    "        reverseText = ''.join(newt)\n",
    "        return max(self.maxRepOpt(text), self.maxRepOpt(reverseText))\n",
    "\n",
    "    def maxRepOpt(self, text: str) -> int:\n",
    "        N = len(text)\n",
    "        lenOfRepeateStartAt = [1]*N\n",
    "        mdict = defaultdict(int)\n",
    "\n",
    "        rst = 1\n",
    "        i = j = 0\n",
    "        while j < N:\n",
    "            while j < N and text[j] == text[i]:\n",
    "                j += 1\n",
    "            if j <= N:\n",
    "                lenOfRepeateStartAt[i] = j-i\n",
    "                mdict[text[i]] += j-i\n",
    "                rst = max(rst, j-i)\n",
    "                i = j\n",
    "\n",
    "        i = 0\n",
    "        while i < N:\n",
    "            j = lenOfRepeateStartAt[i] + i\n",
    "            mlen = j-i\n",
    "            if j < N:\n",
    "                if mdict[text[i]] > mlen:\n",
    "                    mlen += 1\n",
    "                if j+1 < N and text[j+1] == text[i]:\n",
    "                    newj = lenOfRepeateStartAt[j+1] + j+1\n",
    "                    mlen = lenOfRepeateStartAt[j+1] + lenOfRepeateStartAt[i]\n",
    "                    if mlen < mdict[text[i]]:\n",
    "                        mlen += 1\n",
    "            rst = max(rst, mlen)\n",
    "            i = j\n",
    "        return rst\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxRepOpt1(self, text: str) -> int:\n",
    "        group=[text[0]]\n",
    "        lenth=[1]\n",
    "        i=0\n",
    "        l=len(text)\n",
    "        for j in range(1,l):\n",
    "            if text[j]==text[j-1]:\n",
    "                lenth[i]+=1\n",
    "            else:\n",
    "                group.append(text[j])\n",
    "                i+=1\n",
    "                lenth.append(1)\n",
    "        maxlen=max(lenth)\n",
    "        k=len(group)\n",
    "        for j in range(k-1):\n",
    "            if group[j] in group[:j] or group[j] in group[j+1:]:\n",
    "                if j<k-2:\n",
    "                    if group[j]==group[j+2] and lenth[j+1]==1:\n",
    "                        if group[j] in group[j+3:] or group[j] in group[:j]:\n",
    "                            maxlen=max(maxlen,lenth[j]+lenth[j+2]+1)\n",
    "                        else:\n",
    "                            maxlen=max(maxlen,lenth[j]+lenth[j+2])\n",
    "                maxlen=max(maxlen,lenth[j]+1)\n",
    "        if group[k-1] in group[:k-1]:\n",
    "            maxlen=max(maxlen,lenth[k-1]+1)\n",
    "        return maxlen"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxRepOpt1(self, text: str) -> int:\n",
    "        def find(c):\n",
    "            rec = []\n",
    "            i = 0\n",
    "            while i < len(text):\n",
    "                if text[i] == c:\n",
    "                    l = i\n",
    "                    while i < len(text) and text[i] == c:\n",
    "                        i += 1\n",
    "                    rec.append((l, i - 1))  # 求出所有字符c的区间\n",
    "                else:\n",
    "                    i += 1\n",
    "            res = 0\n",
    "            for i in range(len(rec)):\n",
    "                if len(rec) > 1:\n",
    "                    res = max(res, rec[i][1] - rec[i][0] + 2)\n",
    "                else:\n",
    "                    res = max(res, rec[i][1] - rec[i][0] + 1)\n",
    "                if i >= 1 and rec[i][0] - 2 == rec[i - 1][1]:\n",
    "                    if len(rec) >= 3:\n",
    "                        res = max(res, rec[i][1] - rec[i][0] + 1 + rec[i - 1][1] - rec[i - 1][0] + 1 + 1)\n",
    "                    else:\n",
    "                        res = max(res, rec[i][1] - rec[i][0] + 1 + rec[i - 1][1] - rec[i - 1][0] + 1)\n",
    "            return res\n",
    " \n",
    "        res = 0\n",
    "        for i in range(26):\n",
    "            char = chr(ord('a') + i)\n",
    "            res = max(res, find(char))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxRepOpt1(self, text: str) -> int:\n",
    "        record = {}\n",
    "        near = {}\n",
    "        cur = \"\"\n",
    "        max_num = 0\n",
    "        for i in range(len(text)):\n",
    "            if text[i] != cur:\n",
    "                if text[i] not in record:\n",
    "                    record[text[i]] = [] \n",
    "                    record[text[i]].append(1)\n",
    "                    near[text[i]] = []\n",
    "                    near[text[i]].append(False)\n",
    "                else:\n",
    "                    record[text[i]].append(1)\n",
    "                    if text[i-2]==text[i]:\n",
    "                        near[text[i]].append(True)\n",
    "                    else:\n",
    "                        near[text[i]].append(False)\n",
    "                cur = text[i]\n",
    "            else:\n",
    "                record[text[i]][-1]+=1\n",
    "        for i in record:\n",
    "            if len(record[i]) == 1:\n",
    "                # print(max_num)\n",
    "                max_num = max(max_num,record[i][0])\n",
    "                continue\n",
    "            for m in range(len(record[i])):\n",
    "                if near[i][m]:\n",
    "                    if len(near[i])>2:\n",
    "                        max_num = max(max_num,record[i][m]+record[i][m-1]+1)\n",
    "                    else:\n",
    "                        max_num = max(max_num,record[i][m]+record[i][m-1])\n",
    "                else:\n",
    "                    max_num = max(max_num,record[i][m]+1)\n",
    "        # print(record)\n",
    "        # print(near)\n",
    "        # print(max_num)\n",
    "        return max_num"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxRepOpt1(self, text: str) -> int:\n",
    "        c,text=Counter(text),text+\"!\"\n",
    "        def f(x):\n",
    "            a,p=[],-1\n",
    "            for i,v in enumerate(text):\n",
    "                if v!=x :\n",
    "                   if p!=-1:\n",
    "                       a.append((p,i-1))\n",
    "                       p=-1\n",
    "                elif p==-1: p=i\n",
    "            ret=0\n",
    "            for i in range(len(a)):\n",
    "                ret=max(ret,a[i][1]-a[i][0]+1) \n",
    "                if i and a[i][0]-a[i-1][1]==2:\n",
    "                    ret=max(ret,a[i][1]-a[i-1][0])\n",
    "            return min(ret+1,c[x])\n",
    "        return max(f(i) for i in string.ascii_lowercase)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxRepOpt1(self, text: str) -> int:\n",
    "        stack=[]\n",
    "        s=''\n",
    "        ret=0\n",
    "        dic=Counter()\n",
    "        di=Counter()\n",
    "        for i in range(len(text)):\n",
    "            if s=='' or text[i]==s[-1]:\n",
    "                s+=text[i]\n",
    "            else:\n",
    "                stack.append(s)\n",
    "                di[s[-1]]+=1\n",
    "                s=text[i]\n",
    "        stack.append(s)\n",
    "        di[s[-1]]+=1\n",
    "        print(di)\n",
    "        for i in range(len(stack)):\n",
    "            if i==0 or i==1 or dic[stack[i][-1]]==0:\n",
    "                ret=max(ret,len(stack[i]))\n",
    "                dic[stack[i][-1]]=len(stack[i])\n",
    "            else:\n",
    "                if len(stack[i])>dic[stack[i][-1]]:\n",
    "                    dic[stack[i][-1]]=len(stack[i])\n",
    "                if stack[i-2][-1]==stack[i][-1] and len(stack[i-1])==1:\n",
    "                    if di[stack[i][-1]]>2:\n",
    "                        ret=max(ret,len(stack[i])+len(stack[i-2])+1)\n",
    "                    else:\n",
    "                        ret=max(ret,len(stack[i])+len(stack[i-2]))\n",
    "                else:\n",
    "                    ret=max(ret,dic[stack[i][-1]]+1)\n",
    "        return ret\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "                            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxRepOpt1(self, text: str) -> int:\n",
    "        \n",
    "        \n",
    "        \n",
    "        # my solution ... 68 ms ... 60 % ... 16.8 MB ... 27 %\n",
    "        #  time: O(n)\n",
    "        # space: O(n)\n",
    "        \n",
    "        A, sidx = [], 0\n",
    "        f = {text[sidx]: 1}\n",
    "        for eidx in range(len(text)):\n",
    "            if text[sidx] != text[eidx]:\n",
    "                A.append(text[sidx:eidx])\n",
    "                sidx = eidx\n",
    "                f[text[sidx]] = f.get(text[sidx], 0) + 1\n",
    "        A.append(text[sidx:])\n",
    "        if len(A) == 1:\n",
    "            return len(text)\n",
    "        res = 0\n",
    "        for i, s in enumerate(A):\n",
    "            if f[s[0]] == 1:                                                        # 最大化本段\n",
    "                res = max(res, len(s))\n",
    "            else:\n",
    "                res = max(res, len(s) + 1)\n",
    "            if len(s) == 1 and 0 < i < len(A)-1 and A[i-1][0] == A[i+1][0]:         # 最大化邻段\n",
    "                if f[A[i-1][0]] >= 3:\n",
    "                    res = max(res, len(A[i-1]) + 1 + len(A[i+1]))\n",
    "                else:\n",
    "                    res = max(res, len(A[i-1]) + len(A[i+1]))                       # 'aaabaaa' ==> 'aaaaaab'\n",
    "        return res\n",
    "        \n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxRepOpt1(self, text: str) -> int:\n",
    "        n = len(text)\n",
    "        res = 1\n",
    "        for i in range(26):\n",
    "            c = chr(ord('a') + i)\n",
    "            tmp = []\n",
    "            l = 0\n",
    "            while l < n:\n",
    "                if text[l] != c:\n",
    "                    l += 1\n",
    "                else:\n",
    "                    r = l\n",
    "                    while r < n and text[r] == c:\n",
    "                        r += 1\n",
    "                    tmp.append((l, r - 1, r - l))\n",
    "                    l = r + 1\n",
    "            \n",
    "            k = len(tmp)\n",
    "            if k == 0:\n",
    "                continue\n",
    "\n",
    "            print(c, tmp)\n",
    "            if k == 1:\n",
    "                res = max(res, tmp[0][2])\n",
    "            else:\n",
    "                for j in range(k):\n",
    "                    res = max(res, tmp[j][2] + 1)\n",
    "                    if j > 0 and tmp[j][0] - tmp[j - 1][1] == 2:\n",
    "                        res = max(res, tmp[j][2] + tmp[j - 1][2] + int(k > 2))\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxRepOpt1(self, text: str) -> int:\n",
    "        ans = 0\n",
    "        n = len(text)\n",
    "        mp = collections.defaultdict(list)\n",
    "        for i in range(n):\n",
    "            mp[text[i]].append(i)\n",
    "        for x in mp.values():\n",
    "            l = 0\n",
    "            for r in range(len(x)):\n",
    "                while x[r] - x[l] > r - l + 1:\n",
    "                    l += 1\n",
    "                ans = max(ans, r - l + 1 + (l > 0 or r < len(x) - 1))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxRepOpt1(self, text: str) -> int:\n",
    "        dic=defaultdict(list)\n",
    "        for i,s in enumerate(text):\n",
    "            dic[s].append(i)\n",
    "        l,l1,r,n=0,0,0,len(text)\n",
    "        cnt=0\n",
    "        while l<n:\n",
    "            while l1<n and text[l1]==text[l]: l1+=1\n",
    "            r=l1+1\n",
    "            while r<n and text[r]==text[l]: r+=1\n",
    "            if dic[text[l]][-1]>=r or dic[text[l]][0]<l: cnt=max(cnt,r-l)\n",
    "            else: cnt=max(cnt,r-l-1)\n",
    "            l=l1\n",
    "        return cnt "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxRepOpt1(self, text: str) -> int:\n",
    "        dic=defaultdict(list)\n",
    "        for i,s in enumerate(text):\n",
    "            dic[s].append(i)\n",
    "        l,l1,r,n=0,0,0,len(text)\n",
    "        cnt=0\n",
    "        while l<n:\n",
    "            while l1<n and text[l1]==text[l]:\n",
    "                l1+=1\n",
    "            r=l1+1\n",
    "            while r<n and text[r]==text[l]:\n",
    "                r+=1\n",
    "            if dic[text[l]][-1]>=r or dic[text[l]][0]<l: \n",
    "                cnt=max(cnt,r-l)\n",
    "            else:\n",
    "                cnt=max(cnt,r-l-1)\n",
    "            l=l1\n",
    "        return cnt "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxRepOpt1(self, text1: str) -> int:\n",
    "        def f(text):\n",
    "            n = len(text)\n",
    "            d = {}\n",
    "            for i,x in enumerate(text):\n",
    "                d[x] = d.get(x,[])\n",
    "                d[x].append(i)\n",
    "            if len(d) == n:\n",
    "                return 1\n",
    "            elif len(d) == 1:\n",
    "                return n\n",
    "            else:\n",
    "                ans = 1\n",
    "                i = 0\n",
    "                while(i<n-1):\n",
    "                    x = text[i]                \n",
    "                    cnt = 1\n",
    "                    j = i + 1\n",
    "                    ch = 0\n",
    "                    while(j<n):  \n",
    "                        if text[j] == x:\n",
    "                            if ch and j == d[x][-1]:\n",
    "                                cnt -= 1                        \n",
    "                        elif j<d[x][-1] and ch == 0:\n",
    "                            ch = j\n",
    "                        elif j >= n-1 or ch or text[j+1] != x:\n",
    "                            ans = max(ans,cnt)\n",
    "                            i = ch if ch else j\n",
    "                            break\n",
    "                        else:\n",
    "                            ch = j       \n",
    "                        cnt += 1                     \n",
    "                        j += 1\n",
    "                        ans = max(ans,cnt)\n",
    "                        if j >n-2:\n",
    "                            i = ch if ch else j\n",
    "                return ans\n",
    "        a = f(text1)\n",
    "        t = list(text1)\n",
    "        t.reverse()\n",
    "        t = ''.join(t)\n",
    "        return max(a,f(t))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxRepOpt1(self, text: str) -> int:\n",
    "        current_char=text[0]\n",
    "        count=0\n",
    "        templist=[]\n",
    "        charcount=Counter(c for c in text)\n",
    "        result=1\n",
    "        for c in  text:\n",
    "            if c!= current_char:\n",
    "                templist.append((current_char,count))\n",
    "                current_char=c \n",
    "                count=1\n",
    "            else:\n",
    "                count+=1\n",
    "        templist.append((current_char,count))\n",
    "        length=len(templist)\n",
    "        for i in range(length):\n",
    "            ctemp=0\n",
    "            if i+1<length :\n",
    "                if templist[i+1][1]==1 and i+2<length and templist[i][0]==templist[i+2][0]:\n",
    "                    ctemp=min(templist[i][1]+templist[i+2][1]+1,charcount[templist[i][0]])\n",
    "                else:\n",
    "                    ctemp=min(templist[i][1]+1,charcount[templist[i][0]])\n",
    "            elif i!=0:\n",
    "                ctemp=min(templist[i][1]+1,charcount[templist[i][0]])\n",
    "            else:\n",
    "                ctemp=templist[i][1]\n",
    "\n",
    "            result=max(result,ctemp)\n",
    "        return result\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxRepOpt1(self, text: str) -> int:\n",
    "        d = collections.defaultdict(list)\n",
    "        cnt = collections.defaultdict(int)\n",
    "        for i in text:\n",
    "            cnt[i] += 1\n",
    "            if i not in d.keys() or d[i][-1] < 0:\n",
    "                d[i].append(1)\n",
    "            else:\n",
    "                d[i][-1] += 1\n",
    "            for k, j in d.items():\n",
    "                if k == i:\n",
    "                    continue\n",
    "                if j[-1] < 0:\n",
    "                    j[-1] -= 1\n",
    "                else:\n",
    "                    j.append(-1)\n",
    "        res = -1\n",
    "        for k, v in d.items():\n",
    "            n = len(v)\n",
    "            for i in range(n):\n",
    "                if v[i] == -1:\n",
    "                    tmp = 1\n",
    "                    tmp += v[i - 1] if i > 0 else 0\n",
    "                    tmp += v[i + 1] if i < n - 1 else 0\n",
    "                    if tmp > cnt[k]:\n",
    "                        tmp = cnt[k]\n",
    "                    res = max(res, tmp)\n",
    "        for k, v in d.items():\n",
    "            res = max(min(cnt[k], max(v) + 1), res)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxRepOpt1(self, text: str) -> int:\n",
    "        lookup = defaultdict(list)\n",
    "        for i, c in enumerate(text):\n",
    "            if i == 0 or text[i - 1] != c:\n",
    "                lookup[c].append((i, 1))\n",
    "            else:\n",
    "                lookup[c][-1] = (lookup[c][-1][0], lookup[c][-1][1] + 1)\n",
    "        maxWindowSize = 0\n",
    "        for c, l in lookup.items():\n",
    "            for i, block in enumerate(l):\n",
    "                if i > 0 and block[0] == l[i - 1][0] + l[i - 1][1] + 1:\n",
    "                    maxWindowSize = max(maxWindowSize, block[1] + l[i - 1][1] + (1 if len(l) > 2 else 0))\n",
    "                else:\n",
    "                    maxWindowSize = max(maxWindowSize, block[1] + (1 if len(l) > 1 else 0))\n",
    "        return maxWindowSize\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxRepOpt1(self, text: str) -> int:\n",
    "        \n",
    "        n = len(text)\n",
    "        K = defaultdict(list)\n",
    "        for i in range(n):\n",
    "            K[text[i]].append(i)\n",
    "\n",
    "        def cal(text):\n",
    "            T = [1] * n\n",
    "            for i in range(n):\n",
    "                P = 0\n",
    "                for j in range(i + 1, n):\n",
    "                    if text[j] == text[i] or P == 0:\n",
    "                        T[i] += 1\n",
    "                        if text[j] != text[i]:\n",
    "                            P += 1\n",
    "                    else:\n",
    "                        break\n",
    "                if P == 1 and len(K[text[i]]) < T[i]:\n",
    "                    T[i] -= 1\n",
    "            return T\n",
    "        \n",
    "        T1 = cal(text)\n",
    "        T2 = cal(list(reversed(text)))\n",
    "        \n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            ans = max(ans, max(T1[i], T2[i]))\n",
    "\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxRepOpt1(self, text: str) -> int:\n",
    "        lb = [(x, len(list(n))) for x, n in groupby(text)]\n",
    "        ngs = len(lb)\n",
    "        cnts = Counter(text)\n",
    "        maxlen = 1\n",
    "        for i, (x, lgh) in enumerate(lb):\n",
    "            if i < ngs - 2 and lb[i + 1][1] == 1 and lb[i + 2][0] == x:\n",
    "                lgh += lb[i + 2][1]\n",
    "            lgh += cnts[x] > lgh\n",
    "            maxlen = max(maxlen, lgh)\n",
    "        return maxlen\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxRepOpt1(self, text: str) -> int:\n",
    "        # 简化最后一个连续串的处理，在末尾加了一个空格字符\n",
    "        text = text + ' '\n",
    "        n = len(text)\n",
    "        chars = {}\n",
    "        i, pre = 0, text[0]\n",
    "        # 最长的单个重复串，有可能有多个\n",
    "        maxOne = [pre]\n",
    "        maxOneLength = 1\n",
    "        # 最长的两个子串中间只有一个不同字符的串，有可能有多个\n",
    "        maxTwo = []\n",
    "        maxTwoLength = 1\n",
    "        for j in range(1, n):\n",
    "            if text[j] != pre:\n",
    "                if pre not in chars:\n",
    "                    chars[pre] = [[j, j - i]]\n",
    "                else:\n",
    "                    # 更新两个相邻子串(中间只有一个不同字符)\n",
    "                    if chars[pre][-1][0] + 1 == i:\n",
    "                        length = chars[pre][-1][1] + j - i\n",
    "                        if length > maxTwoLength:\n",
    "                            maxTwo = [pre]\n",
    "                            maxTwoLength = length\n",
    "                        elif length == maxTwoLength:\n",
    "                            maxTwo.append(pre)\n",
    "                    chars[pre].append([j, j - i])\n",
    "                # 更新单个重复串\n",
    "                if j - i > maxOneLength:\n",
    "                    maxOne = [pre]\n",
    "                    maxOneLength = j - i\n",
    "                elif j - i == maxOneLength:\n",
    "                    maxOne.append(pre)\n",
    "                i, pre = j, text[j]\n",
    "\n",
    "        # 如果其它位置还有和单个重复串相同的字符，则可以交换过来使总长度加1\n",
    "        for c in maxOne:\n",
    "            if len(chars[c]) > 1:\n",
    "                maxOneLength += 1\n",
    "                break\n",
    "        # 如果其它位置还有和中间只有一个不同字符的两个子串相同的字符，则可以交换过来使总长度加1\n",
    "        for c in maxTwo:\n",
    "            if len(chars[c]) > 2:\n",
    "                maxTwoLength += 1\n",
    "                break\n",
    "        return max(maxOneLength, maxTwoLength)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxRepOpt1(self, text: str) -> int:\n",
    "        \n",
    "        n = len(text)\n",
    "        K = defaultdict(list)\n",
    "        for i in range(n):\n",
    "            K[text[i]].append(i)\n",
    "\n",
    "        def cal(text):\n",
    "            T = [1] * n\n",
    "            for i in range(n):\n",
    "                P = 0\n",
    "                for j in range(i + 1, n):\n",
    "                    if text[j] == text[i] or P == 0:\n",
    "                        T[i] += 1\n",
    "                        if text[j] != text[i]:\n",
    "                            P += 1\n",
    "                    else:\n",
    "                        break\n",
    "                if P == 1 and len(K[text[i]]) < T[i]:\n",
    "                    T[i] -= 1\n",
    "            return T\n",
    "        \n",
    "        T1 = cal(text)\n",
    "        T2 = cal(list(reversed(text)))\n",
    "        return max(max(T1),max(T2))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxRepOpt1(self, text: str) -> int:\n",
    "        group = [(x, len(list(y))) for x, y in groupby(text)]\n",
    "        cnt = Counter(text)\n",
    "        ans = 0\n",
    "        for i, (x, y) in enumerate(group):\n",
    "            if i < len(group) - 2 and group[i + 1][1] == 1 and group[i + 2][0] == x:\n",
    "                cur = y + group[i + 2][1] + 1\n",
    "                ans = max(ans, cur - 1 if cnt[x] < cur else cur)                 \n",
    "            else:\n",
    "                ans = max(ans, y if cnt[x] == y else y + 1)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "可以swap chars in the text, 求出最长的repeated chars (substring)\n",
    "\n",
    "创建map存储该字符出现的位置\n",
    "ababa\n",
    "{'a': [0, 2, 4], 'b': [1, 3]}\n",
    "遍历index的list, 从第二个数开始遍历，\n",
    "比较前一个数和当前的index数，看他们是否是连续的，是连续的就递增count\n",
    "如果他们之间只有一个间隔，我们就用prev_count存储已经计算出的count的个数\n",
    "aaabbaaa （第三个a和第六个a之间差两个，就记录之前的a count是3\n",
    "如果他们之间不只一个间隔，我们就不考虑之前的substring\n",
    "\n",
    "遍历完这个字符后[0, 2, 4], 我们就看这个字符能产生最长的length是什么\n",
    "如果字符出现的次数大于max_Count，则可以将任何位置的字符交换到最长子串中 就是max_count + 1\n",
    "\"\"\"\n",
    "from collections import defaultdict\n",
    "\n",
    "class Solution:\n",
    "    def maxRepOpt1(self, text: str) -> int:\n",
    "        if not text: return 0\n",
    "\n",
    "        char_to_indexes = defaultdict(list)\n",
    "\n",
    "        for i in range(len(text)):\n",
    "            char_to_indexes[text[i]].append(i)\n",
    "\n",
    "        print(char_to_indexes)\n",
    "\n",
    "        maxLen = 0\n",
    "        for indexes in char_to_indexes.values():\n",
    "            count = 1 # 记录当前字符的连续出现次数\n",
    "            maxCount = 1 # 记录最大的连续出现次数\n",
    "            prevCount = 0 # 记录上一段的连续出现次数\n",
    "            for i in range(1, len(indexes)):\n",
    "                if indexes[i] == indexes[i - 1] + 1: # 连续出现\n",
    "                    count += 1\n",
    "                else: # 不连续出现\n",
    "                    if indexes[i] == indexes[i - 1] + 2: # 只有一个字符间隔，可以通过一次交换合并\n",
    "                        prevCount = count\n",
    "                    else: # 有多个字符间隔，不能合并\n",
    "                        prevCount = 0\n",
    "                    count = 1\n",
    "                \n",
    "                # 最大的count数量\n",
    "                maxCount = max(maxCount, prevCount + count)\n",
    "            \n",
    "            # 如果字符出现的次数大于max_Count，则可以将任何位置的字符交换到最长子串中\n",
    "            maxLen = max(maxLen, maxCount + (1 if len(indexes) > maxCount else 0))\n",
    "        \n",
    "        return maxLen\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxRepOpt1(self, text: str) -> int:\n",
    "        char_pos = {}\n",
    "        for i,c in enumerate(list(text)):\n",
    "            if c not in char_pos:\n",
    "                char_pos[c] = []\n",
    "            char_pos[c].append(i)\n",
    "        ans = 0\n",
    "        \n",
    "        for key,seq in char_pos.items():\n",
    "            # 连续的部分合并\n",
    "            path = []\n",
    "            idx = 0\n",
    "            while idx<len(seq):\n",
    "                start = seq[idx]\n",
    "                while idx<len(seq)-1 and seq[idx+1]-seq[idx]==1:\n",
    "                    idx+=1\n",
    "                path.append((start,seq[idx]))\n",
    "                idx+=1\n",
    "            # print(key,path)\n",
    "            # 遍历path，获得最长可得的单字符串\n",
    "            res = 0\n",
    "            if len(path)==1:\n",
    "                res = path[0][1]-path[0][0]+1\n",
    "            else:\n",
    "                for i in range(len(path)):\n",
    "                    res = max(res,path[i][1]-path[i][0]+2)\n",
    "                    if i<len(path)-1:\n",
    "                        if path[i][1]+2==path[i+1][0]:\n",
    "                            # print(path)\n",
    "                            # 结合\n",
    "                            temp = path[i][1]-path[i][0]+2+path[i+1][1]-path[i+1][0]\n",
    "                            if len(path)>2:\n",
    "                                temp+=1\n",
    "                            res = max(res,temp)\n",
    "\n",
    "            ans = max(ans,res)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "  def maxRepOpt1(self, text: str) -> int:\n",
    "        group = [(x, len(list(y))) for x, y in groupby(text)]\n",
    "        count = Counter(text)\n",
    "        max_len = 0\n",
    "        for i, (x, y) in enumerate(group):\n",
    "            if i < len(group) - 2 and group[i + 1][1] == 1 and group[i + 2][0] == x:\n",
    "                cur = y + group[i + 2][1] + 1\n",
    "                max_len = max(max_len, cur - 1 if count[x] < cur else cur)                 \n",
    "            else:\n",
    "                max_len = max(max_len, y if count[x] == y else y + 1)\n",
    "        return max_len\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxRepOpt1(self, text: str) -> int:\n",
    "        # 记录所有字母出现的位置\n",
    "        char_pos = {}\n",
    "        for i,c in enumerate(list(text)):\n",
    "            if c not in char_pos:\n",
    "                char_pos[c] = []\n",
    "            char_pos[c].append(i)\n",
    "        ans = 0\n",
    "        \n",
    "        for key,seq in char_pos.items():\n",
    "            # 将连续的部分合并成范围\n",
    "            path = []\n",
    "            idx = 0\n",
    "            while idx<len(seq):\n",
    "                start = seq[idx]\n",
    "                while idx<len(seq)-1 and seq[idx+1]-seq[idx]==1:\n",
    "                    idx+=1\n",
    "                path.append((start,seq[idx]))\n",
    "                idx+=1\n",
    "            # print(key,path)\n",
    "            # 遍历path，获得最长可得的单字符串\n",
    "            res = 0\n",
    "            # 如果key对应的范围只有一个，则无法通过交换字母拓展其对应的单字符串长度\n",
    "            if len(path)==1:\n",
    "                res = path[0][1]-path[0][0]+1\n",
    "            else:\n",
    "                # 遍历所有的范围\n",
    "                for i in range(len(path)):\n",
    "                    # 当前范围通过交换，至少能达到这个范围的长度+1\n",
    "                    res = max(res,path[i][1]-path[i][0]+2)\n",
    "                    if i<len(path)-1:\n",
    "                        if path[i][1]+2==path[i+1][0]:\n",
    "                            # 第i个范围和第i+1个范围头尾只差1，可以通过交换拼在一起\n",
    "                            temp = path[i][1]-path[i][0]+2+path[i+1][1]-path[i+1][0]\n",
    "                            # 如果范围只有两个，则只能拼接，不能+1\n",
    "                            # 举例 aaabaaa， ababa\n",
    "                            if len(path)>2:\n",
    "                                temp+=1\n",
    "                            res = max(res,temp)\n",
    "\n",
    "            ans = max(ans,res)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "  def maxRepOpt1(self, text: str) -> int:\n",
    "        group = [(x, len(list(y))) for x, y in groupby(text)]\n",
    "        cnt = Counter(text)\n",
    "        max_len = 0\n",
    "        for i, (x, y) in enumerate(group):\n",
    "            if i < len(group) - 2 and group[i + 1][1] == 1 and group[i + 2][0] == x:\n",
    "                cur = y + group[i + 2][1] + 1\n",
    "                max_len = max(max_len, cur - 1 if cnt[x] < cur else cur)                 \n",
    "            else:\n",
    "                max_len = max(max_len, y if cnt[x] == y else y + 1)\n",
    "        return max_len\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxRepOpt1(self, text: str) -> int:\n",
    "        import itertools\n",
    "        cnt = Counter(text)\n",
    "        char_len = [(k, len(list(lst))) for k, lst in itertools.groupby(text)]\n",
    "        print(char_len)\n",
    "        res = max(min(t+1, cnt[k]) for k, t in char_len)\n",
    "        for i in range(1, len(char_len)-1):\n",
    "            if char_len[i-1][0] == char_len[i+1][0] and char_len[i][1] == 1:\n",
    "                res = max(res, min(cnt[char_len[i-1][0]], char_len[i-1][1] + char_len[i+1][1] + 1))\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxRepOpt1(self, text: str) -> int:\n",
    "        # 统计每个字符出现的频次\n",
    "        count = collections.Counter(text)\n",
    "\n",
    "        # 将队列整理成块\n",
    "        queue = []\n",
    "        for ch in text:\n",
    "            if not queue or ch != queue[-1][0]:\n",
    "                queue.append([ch, 1])\n",
    "            else:\n",
    "                queue[-1][1] += 1\n",
    "\n",
    "        ans = 0\n",
    "\n",
    "        # 计算最长子串\n",
    "        for i in range(len(queue)):\n",
    "            elem = queue[i]\n",
    "            length = elem[1]\n",
    "            if i + 2 < len(queue):\n",
    "                if queue[i + 1][1] == 1 and elem[0] == queue[i + 2][0]:\n",
    "                    length += queue[i + 2][1]\n",
    "            if length < count[elem[0]]:\n",
    "                length += 1\n",
    "            ans = max(ans, length)\n",
    "\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxRepOpt1(self, text: str) -> int:\n",
    "        \n",
    "        dct = Counter(text)\n",
    "        lst =[]\n",
    "        pre = text[0]\n",
    "        cnt = 1\n",
    "        for w in text[1:]:\n",
    "            if w == pre:\n",
    "                cnt += 1\n",
    "            else:\n",
    "                lst.append([pre, cnt])\n",
    "                cnt = 1\n",
    "                pre = w\n",
    "        lst.append([pre, cnt])\n",
    "        ans = max(x for _, x in lst)\n",
    "        m = len(lst)\n",
    "        for i in range(m):\n",
    "            w, cnt = lst[i]\n",
    "            if dct[w] > cnt:\n",
    "                if cnt +1>ans:\n",
    "                    ans = cnt+1\n",
    "            if cnt == 1 and i-1>=0 and i+1<m and lst[i-1][0] == lst[i+1][0]:\n",
    "                w = lst[i-1][0]\n",
    "                a = lst[i-1][1] + lst[i+1][1]\n",
    "                if dct[w] > a:\n",
    "                    a += 1\n",
    "                if a > ans:\n",
    "                    ans =a\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxRepOpt1(self, text: str) -> int:\n",
    "        cnt = Counter(text)\n",
    "        g = [[len(list(t)), s] for s, t in groupby(text)]\n",
    "        ans = max(g)[0]\n",
    "        if len(g) >= 3:\n",
    "            for i in range(len(g) - 2):\n",
    "                a, b, c = g[i: i + 3]\n",
    "                if a[1] == c[1] and b[0] == 1:\n",
    "                    ans = max(ans, min(a[0] + c[0] + 1, cnt[a[1]]))\n",
    "            for x, y in g:\n",
    "                ans = max(ans, min(x + 1, cnt[y]))\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def maxRepOpt1(slef,text)->int:\n",
    "        A = [[c, len(list(g))] for c, g in groupby(text)]\n",
    "        count = Counter(text)\n",
    "        res = max(min(k + 1, count[A[i][0]]) for i, (c, k) in enumerate(A))\n",
    "        for i in range(1, len(A) - 1):\n",
    "            if A[i - 1][0] == A[i + 1][0] and A[i][1] == 1:\n",
    "                res = max(res, A[i - 1][1] + A[i + 1][1] + int(count[A[i - 1][0]] > A[i - 1][1] + A[i + 1][1]))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import Counter\n",
    "class Solution:\n",
    "    def maxRepOpt1(self, text: str) -> int:\n",
    "        n=len(text)\n",
    "        if n==1: return 1\n",
    "        newtext=[]\n",
    "        c=Counter(text)\n",
    "        res=1\n",
    "        for i in range(1,n):\n",
    "            if text[i]==text[i-1]:\n",
    "                res+=1\n",
    "            elif text[i]!=text[i-1]:\n",
    "                newtext.append((text[i-1],res))\n",
    "                res=1\n",
    "        newtext.append((text[-1],res))\n",
    "        print(newtext)\n",
    "        newn=len(newtext)\n",
    "        ans=max(newtext[i][1] for i in range(newn))\n",
    "        for i in range(newn-2):\n",
    "            cnt=newtext[i][1]\n",
    "            if newtext[i][0]==newtext[i+2][0] and newtext[i+1][1]==1:\n",
    "                cnt=newtext[i][1]+newtext[i+2][1]\n",
    "                if c[newtext[i][0]]-cnt>0:\n",
    "                    cnt+=1\n",
    "            else:\n",
    "                if c[newtext[i][0]]-newtext[i][1]>0:\n",
    "                    cnt+=1\n",
    "            ans=max(ans,cnt)\n",
    "        if c[newtext[newn-2][0]]-newtext[newn-2][1]>0:\n",
    "            ans=max(ans,newtext[newn-2][1]+1)\n",
    "        if c[newtext[newn-1][0]]-newtext[newn-1][1]>0:\n",
    "            ans=max(ans,newtext[newn-1][1]+1)\n",
    "        return ans\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxRepOpt1(self, text: str) -> int:\n",
    "        cnt = [['#', 1]]\n",
    "        for c in text:\n",
    "            if c == cnt[-1][0]:\n",
    "                cnt[-1][1] += 1\n",
    "            else:\n",
    "                cnt.append([c, 1])\n",
    "        n = len(cnt)\n",
    "        tot = Counter(text)\n",
    "        mx = 1\n",
    "        for _, size in cnt:\n",
    "            size += int(size < tot[_])\n",
    "            if size > mx:\n",
    "                mx = size\n",
    "\n",
    "        \n",
    "        for i in range(1, n - 1):\n",
    "            if cnt[i][1] == 1 and cnt[i - 1][0] == cnt[i + 1][0]:\n",
    "                sm = cnt[i - 1][1] + cnt[i + 1][1]\n",
    "                sm += int(sm < tot[cnt[i - 1][0]])\n",
    "                if sm > mx:\n",
    "                    mx = sm\n",
    "        return mx"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import Counter\n",
    "class Solution:\n",
    "    def maxRepOpt1(self, text: str) -> int:\n",
    "        n=len(text)\n",
    "        if n==1: return 1\n",
    "        newtext=[]\n",
    "        c=Counter(text)\n",
    "        res=1\n",
    "        for i in range(1,n):\n",
    "            if text[i]==text[i-1]:\n",
    "                res+=1\n",
    "            elif text[i]!=text[i-1]:\n",
    "                newtext.append((text[i-1],res))\n",
    "                res=1\n",
    "        newtext.append((text[-1],res))\n",
    "        print(newtext)\n",
    "        newn=len(newtext)\n",
    "        ans=max(newtext[i][1] for i in range(newn))\n",
    "        for i in range(newn-2):\n",
    "            cnt=newtext[i][1]\n",
    "            if newtext[i][0]==newtext[i+2][0] and newtext[i+1][1]==1:\n",
    "                cnt=newtext[i][1]+newtext[i+2][1]\n",
    "                if c[newtext[i][0]]-cnt>0:\n",
    "                    cnt+=1\n",
    "            ans=max(ans,cnt)\n",
    "        for i in range(newn):\n",
    "            cnt=newtext[i][1]\n",
    "            if c[newtext[i][0]]-newtext[i][1]>0:\n",
    "                cnt+=1\n",
    "            ans=max(ans,cnt)\n",
    "        return ans\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxRepOpt1(self, text: str) -> int:\n",
    "        max_length = []\n",
    "        coun_text = Counter(text)\n",
    "        for key in coun_text.keys():\n",
    "            count_arr = []\n",
    "            count = 0\n",
    "            for v in text:\n",
    "                if key == v:\n",
    "                    count += 1\n",
    "                else:\n",
    "                    count_arr.append(count)\n",
    "                    count_arr.append(0)\n",
    "                    count = 0\n",
    "            count_arr.append(count)\n",
    "            max_v2 = max(count_arr)\n",
    "            max_length.append(max_v2)\n",
    "            for max_i , max_v in enumerate(count_arr):\n",
    "                temp = 0\n",
    "                if max_i - 2 >= 0:\n",
    "                    if count_arr[max_i - 2] > 0:\n",
    "                        temp = count_arr[max_i - 2] + max_v\n",
    "                        max_length.append(temp)\n",
    "                        if max_i - 4 >= 0:\n",
    "                            for i in range(max_i - 2):\n",
    "                                if count_arr[i] > 0:\n",
    "                                    max_length.append(temp + 1)\n",
    "                                    break\n",
    "                        if max_i + 2 < len(count_arr):\n",
    "                            for i in range(max_i + 2 , len(count_arr)):\n",
    "                                if count_arr[i] > 0:\n",
    "                                    max_length.append(1 + temp)\n",
    "                                    break\n",
    "                elif max_i > 0:\n",
    "                    for i in range(max_i):\n",
    "                        if count_arr[i] > 0:\n",
    "                            max_length.append(1 + max_v)\n",
    "                            break\n",
    "                if max_i + 2 < len(count_arr):\n",
    "                    if count_arr[max_i + 2] > 0:\n",
    "                        temp = count_arr[max_i + 2] + max_v\n",
    "                        max_length.append(temp)\n",
    "                        if max_i + 4 < len(count_arr):\n",
    "                            for i in range(max_i + 4 , len(count_arr)):\n",
    "                                if count_arr[i] > 0:\n",
    "                                    max_length.append(1 + temp)\n",
    "                                    break\n",
    "                        if max_i - 2 >= 0:\n",
    "                            for i in range(max_i):\n",
    "                                if count_arr[i] > 0:\n",
    "                                    max_length.append(1 + temp)\n",
    "                                    break\n",
    "                elif max_i + 1 < len(count_arr):\n",
    "                    for i in range(max_i + 1 , len(count_arr)):\n",
    "                        if count_arr[i] > 0:\n",
    "                            max_length.append(1 + max_v)\n",
    "                            break\n",
    "        return max(max_length)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxRepOpt1(self, text: str) -> int:\n",
    "        text += '.'\n",
    "        l = []  # 按顺序记录每个分段的字母和分段的长度\n",
    "        d1 = defaultdict(int)  # 统计每种字符有多少段\n",
    "        ans = 0\n",
    "        start = 0\n",
    "        for i, x in enumerate(text[1:], 1):\n",
    "            if text[start] == x:\n",
    "                continue\n",
    "            l.append([text[start], i - start])\n",
    "            d1[text[start]] += 1\n",
    "            start = i\n",
    "        # 统计两段相同字母段，中间仅隔一个其他字母的段总长\n",
    "        for i, [ch, time] in enumerate(l):\n",
    "            if d1[ch] > 1:\n",
    "                ans = max(ans, time + 1)\n",
    "            else:\n",
    "                ans = max(ans, time)\n",
    "            if time != 1 or i == 0 or i == len(l) - 1: continue\n",
    "            if l[i - 1][0] == l[i + 1][0]:\n",
    "                if d1[l[i - 1][0]] > 2:\n",
    "                    ans = max(ans, l[i - 1][1] + l[i + 1][1] + 1)\n",
    "                else:\n",
    "                    ans = max(ans, l[i - 1][1] + l[i + 1][1])\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxRepOpt1(self, text: str) -> int:\n",
    "        if len(text)==1:\n",
    "            return 1\n",
    "        left = 0\n",
    "        right = 1\n",
    "        ans = []\n",
    "        while right < len(text):\n",
    "            if text[right] != text[left]:\n",
    "                ans.append([text[left], right - left])\n",
    "                left = right\n",
    "            right += 1\n",
    "            if right == len(text):\n",
    "                ans.append([text[left], right - left])\n",
    "        res = []\n",
    "        ans1 = sorted(ans, key=lambda x: -x[1])\n",
    "        a = ans1[0][1]\n",
    "        for x in ans1:\n",
    "            if x[1] == a:\n",
    "                if text.count(x[0]) > x[1]:\n",
    "                    res.append(x[1] + 1)\n",
    "                    break\n",
    "            else:\n",
    "                break\n",
    "        if not res:\n",
    "            res.append(a)\n",
    "        for i in range(len(ans) - 2):\n",
    "            if ans[i][0] == ans[i + 2][0] and ans[i + 1][1] == 1:\n",
    "                if text.count(ans[i][0]) > ans[i][1] + ans[i + 2][1]:\n",
    "                    if ans[i][1] + ans[i + 2][1] + 1 > a:\n",
    "                        res.append(ans[i][1] + ans[i + 2][1] + 1)\n",
    "                else:\n",
    "                    if ans[i][1] + ans[i + 2][1] > a:\n",
    "                        res.append(ans[i][1] + ans[i + 2][1])\n",
    "        return max(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxRepOpt1(self, text: str) -> int:\n",
    "        m = [[] for _ in range(26)]\n",
    "        res = 0\n",
    "        n = len(text)\n",
    "        i = 0\n",
    "        while i < n:\n",
    "            start = i\n",
    "            while i + 1 < n and text[i + 1] == text[start]:\n",
    "                i += 1\n",
    "            m[ord(text[start]) - ord('a')].append((start, i))\n",
    "            res = max(res, i - start + 1)\n",
    "            i += 1\n",
    "        for list in m:\n",
    "            n = len(list)\n",
    "            for i in range(n):\n",
    "                if n != 1:\n",
    "                    res = max(res, list[i][1] - list[i][0] + 2)\n",
    "                if i + 1 < n and list[i][1] + 1 == list[i + 1][0] - 1:\n",
    "                    val = list[i][1] - list[i][0] + 1 + \\\n",
    "                        list[i + 1][1] - list[i + 1][0] + 1\n",
    "                    if not (i == 0 and i + 2 == n):\n",
    "                        val += 1\n",
    "                    res = max(res, val)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "class Solution:\n",
    "    def maxRepOpt1(self, text: str) -> int:\n",
    "        hm = defaultdict(list)\n",
    "        res = 0\n",
    "        n = len(text)\n",
    "        curr = text[0]\n",
    "        left = 0\n",
    "        right = 0\n",
    "        for i in range(1, n):\n",
    "            if text[i] == curr:\n",
    "                right += 1\n",
    "            else:\n",
    "                hm[curr].append((left, right, right - left + 1))\n",
    "                curr = text[i]\n",
    "                left = right = i\n",
    "\n",
    "        if right == n:\n",
    "            hm[curr].append((left, right - 1, right - left))\n",
    "        else:\n",
    "            hm[curr].append((left, right, right - left + 1))\n",
    "\n",
    "        for key in hm:\n",
    "            for i in range(len(hm[key])):\n",
    "                res = max(res, hm[key][i][2] + (1 if len(hm.keys()) > 1 and len(hm[key]) > 1 else 0))\n",
    "                if i >= 1 and hm[key][i][0] - hm[key][i - 1][1] == 2:\n",
    "                    res = max(res, hm[key][i][2] + hm[key][i - 1][2] + (1 if len(hm[key]) > 2 else 0))\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxRepOpt1(self, text: str) -> int:\n",
    "        if len(text) == 1 or len(text) == 0:\n",
    "            return len(text)\n",
    "        pattern = []\n",
    "        d = []\n",
    "        count = 1\n",
    "        for i in range(0,len(text)-1):\n",
    "            if text[i+1] == text[i]:\n",
    "                count += 1\n",
    "            else:\n",
    "                pattern.append(count)\n",
    "                d.append(text[i])\n",
    "                count = 1\n",
    "        pattern.append(count)\n",
    "        d.append(text[-1])\n",
    "        if len(pattern) == 1 or len(pattern) == 2:\n",
    "            return max(pattern)\n",
    "        \n",
    "        m = max(pattern)\n",
    "        for i in range(len(pattern)):\n",
    "            if m == pattern[i]:\n",
    "                if text.count(d[i]) > m:\n",
    "                    m = m + 1\n",
    "        if 1 not in pattern:\n",
    "            return m\n",
    "        one = []\n",
    "        loc = []\n",
    "        s = pattern[0]\n",
    "        for i in range(1,len(pattern)-1):\n",
    "            if pattern[i] == 1:\n",
    "                one.append(i)\n",
    "                loc.append(s)\n",
    "            s += pattern[i]\n",
    "        res = 1\n",
    "        print(loc,one,pattern)\n",
    "        for i in range(len(loc)):\n",
    "            pp = one[i]\n",
    "            tp = loc[i]\n",
    "            if text[tp-1] == text[tp+1]:\n",
    "                T = pattern[pp-1]+pattern[pp+1]\n",
    "                if T < text.count(text[tp-1]):\n",
    "                    T = T + 1\n",
    "                if T>res:\n",
    "                    res = T\n",
    "        return max(res,m)\n",
    "\n",
    "            \n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxRepOpt1(self, text: str) -> int:\n",
    "        tmp=[[]for i in range(26)]\n",
    "        i,j=0,0\n",
    "        while j<len(text):\n",
    "            if text[i]==text[j]:\n",
    "                j+=1\n",
    "            else:\n",
    "                tmp[ord(text[i])-ord('a')].append((i,j))\n",
    "                i=j\n",
    "        tmp[ord(text[i])-ord('a')].append((i,j))\n",
    "        ans=0\n",
    "        for i in range(26):\n",
    "            if len(tmp[i])==0:\n",
    "                continue\n",
    "            ans=max(ans,tmp[i][0][1]-tmp[i][0][0])\n",
    "            for j in range(1,len(tmp[i])):\n",
    "                ans=max(ans,tmp[i][j][1]-tmp[i][j][0])\n",
    "                if tmp[i][j][0]-tmp[i][j-1][1]==1:\n",
    "                    if len(tmp[i])>2:\n",
    "                        ans=max(ans,tmp[i][j][1]-tmp[i][j][0]+tmp[i][j-1][1]-tmp[i][j-1][0]+1)\n",
    "                    else:\n",
    "                        ans=max(ans,tmp[i][j][1]-tmp[i][j][0]+tmp[i][j-1][1]-tmp[i][j-1][0])       \n",
    "                else:\n",
    "                    ans=max(ans,tmp[i][j-1][1]-tmp[i][j-1][0]+1)\n",
    "            if len(tmp[i])>1:\n",
    "                ans=max(ans,tmp[i][-1][1]-tmp[i][-1][0]+1)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxRepOpt1(self, text: str) -> int:\n",
    "        c = Counter(text)\n",
    "        d = defaultdict(list)\n",
    "        left = 0\n",
    "        right = 0\n",
    "        for i in range(len(text)):\n",
    "            if text[i] == text[left]:\n",
    "                right = i\n",
    "            else:\n",
    "                d[text[left]].append((left, right))\n",
    "                left = i\n",
    "                right = i\n",
    "        d[text[left]].append((left, right))\n",
    "        ret = 1\n",
    "        for k, l in d.items():\n",
    "            if l[0][1] - l[0][0] + 1 >= ret:\n",
    "                ret = l[0][1] - l[0][0] + 1\n",
    "                if len(l) > 1:\n",
    "                    ret += 1\n",
    "            for i in range(1, len(l)):\n",
    "                if l[i][1] - l[i][0] + 2 > ret:\n",
    "                    ret = l[i][1] - l[i][0] + 2\n",
    "                if l[i][0] - l[i-1][1] == 2:\n",
    "                    ret = max(ret, min(l[i][1] - l[i-1][0] + 1, c[k]))\n",
    "        return ret\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxRepOpt1(self, text: str):\n",
    "        d = defaultdict(list)\n",
    "\n",
    "        left = right = 0\n",
    "        n = len(text)\n",
    "        \n",
    "        for i in range(1, n):\n",
    "            if text[i] == text[i-1]:\n",
    "                right = i\n",
    "            else:\n",
    "                d[text[i-1]].append((left, right))\n",
    "                left = right = i\n",
    "        \n",
    "        d[text[-1]].append((left, right))\n",
    "        res = 0\n",
    "\n",
    "        for v1 in d.values():\n",
    "            nn = len(v1)\n",
    "            for i in range(nn-1):\n",
    "                if v1[i][1] + 2 == v1[i+1][0]:\n",
    "                    if nn > 2:\n",
    "                        res = max(res, v1[i+1][1] - v1[i][0] + 1)\n",
    "                    else:\n",
    "                        res = max(res, v1[i+1][1] - v1[i][0])\n",
    "                else:\n",
    "                    if nn > 1:\n",
    "                        res = max(res, v1[i][1] - v1[i][0] + 2)\n",
    "                    else:\n",
    "                        res = max(res, v1[i][1] - v1[i][0] + 1)\n",
    "            if nn > 1:\n",
    "                res = max(res, v1[-1][1] - v1[-1][0] + 2)\n",
    "            else:\n",
    "                res = max(res, v1[-1][1] - v1[-1][0] + 1)\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxRepOpt1(self, text: str) -> int:\n",
    "        letter2len = defaultdict(list)\n",
    "        letter2len[text[0]].append([0, 1])\n",
    "        for i in range(1, len(text)):\n",
    "            if text[i] == text[i - 1]:\n",
    "                letter2len[text[i]][-1][1] += 1\n",
    "            else:\n",
    "                letter2len[text[i]].append([i, 1])\n",
    "        ans = 0\n",
    "        for letter, s_l in letter2len.items():\n",
    "            if len(s_l) == 1:\n",
    "                ans = max(ans, s_l[0][1])\n",
    "                continue\n",
    "            ans = max(ans, s_l[0][1] + 1)\n",
    "            for i in range(1, len(s_l)):\n",
    "                ans = max(ans, s_l[i][1] + 1)\n",
    "                if sum(s_l[i - 1]) + 1 == s_l[i][0]:\n",
    "                    ans = max(ans, s_l[i - 1][1] + s_l[i][1] + (len(s_l) > 2))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxRepOpt1(self, text: str) -> int:\n",
    "        dic = defaultdict(list)\n",
    "        start = 0\n",
    "        for i, c in enumerate(text):\n",
    "            if c != text[start]:\n",
    "                dic[text[start]].append((start, i))\n",
    "                start = i\n",
    "        dic[text[start]].append((start, len(text)))\n",
    "        res = 0\n",
    "        for tuples in dic.values():\n",
    "            if len(tuples) == 1:\n",
    "                res = max(res, tuples[0][1] - tuples[0][0])\n",
    "            elif len(tuples) == 2:\n",
    "                if tuples[1][0] - tuples[0][1] == 1:\n",
    "                    res = max(res, tuples[1][1] - tuples[1][0] + tuples[0][1] - tuples[0][0])\n",
    "                else:\n",
    "                    res = max([res, tuples[1][1] - tuples[1][0] + 1, tuples[0][1] - tuples[0][0] + 1])\n",
    "            else:\n",
    "                for i in range(len(tuples) - 1):\n",
    "                    if tuples[i + 1][0] - tuples[i][1] == 1:\n",
    "                        res = max(res, tuples[i + 1][1] - tuples[i + 1][0] + tuples[i][1] - tuples[i][0] + 1)\n",
    "                    else:\n",
    "                        res = max(res, tuples[i][1] - tuples[i][0] + 1)\n",
    "                res = max(res, tuples[-1][1] - tuples[-1][0] + 1)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxRepOpt1(self, text: str) -> int:\n",
    "        text = text + ' '\n",
    "        answer = 0 \n",
    "\n",
    "        aa = defaultdict(list)\n",
    "        #定义一个字典记录text中的单字符重复子串的左端点、右端点以及长度\n",
    "        start = 0   #左端点从零开始右端点遍历得到\n",
    "        for end in range(len(text)):    #右端点及长度由遍历得到\n",
    "            if text[end] != text[start]:\n",
    "                aa[text[start]] += [(start, end-1, end-start)]\n",
    "                answer = max(answer, end-start)\n",
    "                start = end\n",
    "        for key in aa:\n",
    "            for curr_index in range(1, len(aa[key])):\n",
    "                curr_start,curr_end,curr_length = aa[key][curr_index]\n",
    "                prev_start,prev_end,prev_length = aa[key][curr_index-1]\n",
    "                answer = max(answer, prev_length+1, curr_length+1)\n",
    "                if prev_end + 2 == curr_start:\n",
    "                    new_length = prev_length + curr_length\n",
    "                    if len(aa[key]) >= 3:\n",
    "                        new_length += 1\n",
    "                    answer = max(answer, new_length)\n",
    "        \n",
    "        return answer\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxRepOpt1(self, text: str) -> int:\n",
    "      d=defaultdict(list)\n",
    "      for i,c in enumerate(text):\n",
    "        l=d[c]\n",
    "        if not l or l[-1][1]!=i-1:\n",
    "          l.append([i,i])\n",
    "        else:\n",
    "          l[-1][1]=i\n",
    "          \n",
    "      ret=0\n",
    "      for l in d.values():\n",
    "        n=len(l)\n",
    "        pv=l[0][1]-l[0][0]+1\n",
    "        ret=max(ret,pv if n==1 else pv+1)\n",
    "        for i in range(1,n):\n",
    "          v=l[i][1]-l[i][0]+1\n",
    "          if l[i][0]-l[i-1][1]==2:\n",
    "            ret=max(ret,pv+v+(1 if n>2 else 0))\n",
    "          else:\n",
    "            ret=max(ret,v+1)\n",
    "          pv=v\n",
    "          \n",
    "      return ret\n",
    "           \n",
    "      "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxRepOpt1(self, text: str) -> int:\n",
    "        ch2pos = {}\n",
    "        str = text\n",
    "        last_ch = str[0]\n",
    "        st = 0\n",
    "        ed = 0\n",
    "        for i in range(1, len(str)):\n",
    "            if str[i] == last_ch:\n",
    "                ed += 1\n",
    "            else:\n",
    "                if last_ch not in ch2pos:\n",
    "                    ch2pos[last_ch] = []\n",
    "                ch2pos[last_ch].append([st, ed])\n",
    "                st = ed = i\n",
    "                last_ch = str[i]\n",
    "        if last_ch not in ch2pos:\n",
    "            ch2pos[last_ch] = []\n",
    "        ch2pos[last_ch].append([st, ed])\n",
    "\n",
    "        max_len = 0\n",
    "        for k in ch2pos:\n",
    "            arr = ch2pos[k]\n",
    "            max_len = max(max_len, arr[0][1] - arr[0][0] + 1) if len(arr) == 1 else max(max_len, arr[0][1] - arr[0][0] + 2)\n",
    "\n",
    "            for i in range(1, len(arr)):\n",
    "                max_len = max(max_len, max_len, arr[i][1] - arr[i][0] + 2)\n",
    "                if arr[i][0] == arr[i-1][1] + 2:\n",
    "                    if len(arr) == 2:\n",
    "                        max_len = max(max_len, arr[i][1] - arr[i-1][0])\n",
    "                    else:\n",
    "                        max_len = max(max_len, arr[i][1] - arr[i-1][0] + 1)\n",
    "        return max_len"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxRepOpt1(self, text: str) -> int:\n",
    "        def f(nums):\n",
    "            return nums[-1] - nums[0]\n",
    "\n",
    "        ans = 0\n",
    "        # {a: [[1, 4], [5, 6]], b: [[0, 1], [4, 5]]}\n",
    "        d = defaultdict(deque)\n",
    "        for i, ch in enumerate(text):\n",
    "            if d[ch] and d[ch][-1][1] == i:\n",
    "                d[ch][-1][1] += 1\n",
    "            else:\n",
    "                d[ch].append([i, i+1])\n",
    "            ans = max(ans, f(d[ch][-1]))\n",
    "\n",
    "        for ch in d:\n",
    "            row = d[ch]\n",
    "            ls = len(row)\n",
    "            for i in range(ls):\n",
    "                if ls > 1:\n",
    "                    ans = max(ans, f(row[i]) + 1)\n",
    "                if i < ls - 1 and row[i][-1] + 1 == row[i+1][0]:\n",
    "                    if ls > 2:\n",
    "                        ans = max(ans, f(row[i]) + f(row[i+1]) + 1)\n",
    "                    else:\n",
    "                        ans = max(ans, f(row[i]) + f(row[i+1]))\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxRepOpt1(self, text: str) -> int:\n",
    "        d = {}\n",
    "        for i in range(len(text)):\n",
    "            if text[i] not in d:\n",
    "                d[text[i]] = []\n",
    "        for a in d:\n",
    "            start = 0\n",
    "            while start!= len(text):\n",
    "                if text[start] == a:\n",
    "                    j = start+1\n",
    "                    while j!=len(text):\n",
    "                        if text[j]!=a:\n",
    "                            break\n",
    "                        j+=1\n",
    "                    end = j-1\n",
    "                    d[a].append([start,end])\n",
    "                    start = end+1\n",
    "                else:\n",
    "                    start += 1\n",
    "        max_l = 1\n",
    "        for a in d:\n",
    "            if len(d[a]) == 1:\n",
    "                max_l = max(max_l,d[a][0][1] - d[a][0][0] +1)\n",
    "            elif len(d[a]) == 2:\n",
    "                if (d[a][1][0] - d[a][0][1]) == 2:\n",
    "                    max_l = max(max_l,d[a][1][1] - d[a][0][0])\n",
    "                else:\n",
    "                    max_l = max(max_l,1+max(d[a][0][1] - d[a][0][0] +1,d[a][1][1] - d[a][1][0] +1))\n",
    "            else:\n",
    "                for i in range(len(d[a])-1):\n",
    "                    if (d[a][i+1][0] - d[a][i][1]) == 2:\n",
    "                        max_l = max(max_l, 1 + d[a][i+1][1] - d[a][i][0])\n",
    "                    else:\n",
    "                        max_l = max(max_l, 1 + max(d[a][i+1][1] - d[a][i+1][0] + 1,d[a][i][1] - d[a][i][0] + 1))\n",
    "        return max_l\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxRepOpt1(self, text: str) -> int:\n",
    "        text = text + ' '\n",
    "        answer = 0 \n",
    "\n",
    "        aa = defaultdict(list)\n",
    "        #定义一个字典记录text中的单字符重复子串的左端点、右端点以及长度\n",
    "        start = 0   #左端点从零开始右端点遍历得到\n",
    "        for end in range(len(text)):    #右端点及长度由遍历得到\n",
    "            if text[end] != text[start]:\n",
    "                aa[text[start]] += [(start, end-1, end-start)]\n",
    "                answer = max(answer, end-start)\n",
    "                start = end\n",
    "        for key in aa:\n",
    "            for curr_index in range(1, len(aa[key])):\n",
    "                curr_start,curr_end,curr_length = aa[key][curr_index]\n",
    "                prev_start,prev_end,prev_length = aa[key][curr_index-1]\n",
    "                answer = max(answer, prev_length+1, curr_length+1)\n",
    "                if prev_end + 2 == curr_start:\n",
    "                    new_length = prev_length + curr_length\n",
    "                    if len(aa[key]) >= 3:\n",
    "                        new_length += 1\n",
    "                    answer = max(answer, new_length)\n",
    "        \n",
    "        return answer\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxRepOpt1(self, text: str) -> int:\n",
    "        data = collections.defaultdict(list)\n",
    "        l, r = 0, 0\n",
    "\n",
    "        idx = 1\n",
    "        while idx < len(text):\n",
    "            ch = text[idx]\n",
    "            if ch != text[r]:\n",
    "                data[text[r]].append([l, r])\n",
    "                l = idx\n",
    "\n",
    "            r = idx\n",
    "            idx += 1\n",
    "        data[text[r]].append([l, r])\n",
    "\n",
    "        if len(data) == 1:\n",
    "            return len(text)\n",
    "        res = 0\n",
    "        for k, v in data.items():\n",
    "            for idx, (a, b) in enumerate(v):\n",
    "                res = max(res, b-a+1)\n",
    "                if len(v) > 1:\n",
    "                    res = max(res, b-a+2)\n",
    "                # print(idx, a, v[idx-1])\n",
    "                if idx and a == v[idx-1][1]+2:\n",
    "                    if len(v) == 2:\n",
    "                        res = max(res, b-v[idx-1][0])\n",
    "                    else:\n",
    "                        res = max(res, b-v[idx-1][0]+1)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def maxRepOpt1(self, text: str) -> int:                     \n",
    "\n",
    "        c = Counter(text)                                       \n",
    "\n",
    "        ch, ct = zip(*[(k, sum(1 for _ in g))                   \n",
    "                       for k, g in groupby(text)])           \n",
    "\n",
    "        n = len(ch)\n",
    "        \n",
    "        ans = max(ct[i]+(ct[i]<c[ch[i]]) for i in range(n))   \n",
    "\n",
    "        for i in range(1, n-1):                                \n",
    "                                                                \n",
    "            if ch[i-1] == ch[i+1] and ct[i] == 1:              \n",
    "                sm = ct[i-1]+ct[i+1]                            \n",
    "                ans = max(ans, sm + (sm < c[ch[i-1]]))        \n",
    "                                                                \n",
    "        return ans                                              \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxRepOpt1(self, text: str) -> int:\n",
    "        # \n",
    "        hashmap = defaultdict(list)\n",
    "        n = len(text)\n",
    "        ans = 0\n",
    "        left, cur = 0, text[0]\n",
    "        for i in range(1, n):\n",
    "            if text[i] != cur:\n",
    "                ans = max(ans, i - left)\n",
    "                hashmap[cur].append((left, i - 1))\n",
    "                cur = text[i]\n",
    "                left = i                 \n",
    "        hashmap[cur].append((left, n - 1))\n",
    "        ans = max(ans, n - left)\n",
    "        for ch, l in hashmap.items():\n",
    "            for i in range(len(l) - 1):\n",
    "                if l[i][1] == l[i + 1][0] - 2:\n",
    "                    if len(l) > 2:\n",
    "                        ans = max(ans, l[i + 1][1] - l[i][0] + 1)\n",
    "                    elif len(l) == 2:\n",
    "                        ans = max(ans, l[i + 1][1] - l[i][0])\n",
    "                else:\n",
    "                    ans = max(ans, l[i][1] - l[i][0] + 2, l[i + 1][1] - l[i + 1][0] + 2)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxRepOpt1(self, text: str) -> int:\n",
    "        dic = defaultdict(list)\n",
    "\n",
    "        tmp = 0\n",
    "        pre = text[0]\n",
    "        for i in range(1, len(text)) :\n",
    "            if text[i] != pre :\n",
    "                dic[pre].append([tmp, i-1])\n",
    "                pre = text[i]\n",
    "                tmp = i\n",
    "        dic[pre].append([tmp, len(text)-1])\n",
    "        ans = 0\n",
    "        for k, v in dic.items():\n",
    "            pre = (-10, -10)\n",
    "            for i in range(len(v)) :\n",
    "                s, e = v[i]\n",
    "                node = (e-s+1)\n",
    "                if pre[1] + 2 == s :\n",
    "                    node += (pre[1]-pre[0]+1)\n",
    "                    if len(v) > 2 :\n",
    "                        node += 1\n",
    "                else :\n",
    "                    if len(v) >= 2 :\n",
    "                        node += 1\n",
    "                ans = max(ans, node)\n",
    "                pre = (s, e)\n",
    "\n",
    "        return ans\n",
    "\n",
    "\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
